package chapter_03;


public class InsertSort extends BubbleSort{
    // 插入排序
    /*
    不变性：在每趟结束时，在将temp位置的项插入后，比out变量下标小的数据项都是局部有序的。
    在第一趟排序中，它最多比较一次，第二趟最多比较两次，依此类推。最后一趟最多，比较N-1次，因此有
    1+2+3+...+N-1 = N*(N-1)/2
    然而，因为在每一趟排序发现插入点之前，平均只有全体数据项的一半真的进行了比较，我们除以二得到
    N*(N-1)/4（插入的那个数据项与有序的数据项比较的话，平均只比较有序数据项的一半）。
    复制的次数大致等于比较的次数。然而，一次复制与一次交换的时间耗费不同，所以相对于随机数据，
    这个算法比冒泡排序快一倍，比选择排序略快。
    在任意情况下，对于随机排序的数据进行插入排序也需要O(N^2)的时间级。
    对于已经有序或基本有序的数据来说，插入排序要好很多。当数据有序的时候，while循环的条件总是假，
    所以它变成了外层循环的一个简单句，执行N-1次。在这种情况下，算法运行只需要O(N)的时间。
    然而，对于逆序排列的数据，每次比较和移动都会执行，所以插入排序不会比冒泡排序快。
    在外层的for循环中，out变量从1开始，向右移动。它标记了未排序部分最左端的数据。而在内层的while循环中，in
    变量从out变量开始，向左移动，直到temp变量小于in所指的数组数据项，或者它已经不能再往左移动为止。
    while循环的每一趟都向右移动了一个已排序的数据项。
     */

    InsertSort(int max) {
        super(max);
    }

    public void sort() {
        int out;
        for (out = 1; out < nElems; out++) {
            long temp = a[out];     // 保存当前索引对应的值
            while (out > 0 && a[out - 1] > temp) {
                a[out] = a[out - 1];// 向后移动一个值
                out--;
            }
            a[out] = temp;          // out的位置正好是需要插入temp值的位置
        }
    }

    public static void main(String[] args) {
        int maxSize = 10;
        BubbleSort arr;
        arr = new InsertSort(maxSize);

        arr.insert(77);
        arr.insert(99);
        arr.insert(44);
        arr.insert(55);
        arr.insert(22);
        arr.insert(88);
        arr.insert(11);
        arr.insert(00);
        arr.insert(66);
        arr.insert(33);
        arr.display();
        arr.sort();
        arr.display();
    }
}
